#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 数据结构定义
typedef struct {
    int weight;
    double value;
} Item;

typedef struct {
    int *selected;
    double total_value;
    int total_weight;
    double time_cost;
    int timeout;  // 是否超时
    long long total_nodes;     // 总节点数
    long long pruned_nodes;    // 剪枝节点数
} Result;

// 全局变量
double best_value = 0;
int best_weight = 0;
int *best_solution;
long long node_count = 0;      // 访问的节点数
long long pruned_count = 0;    // 剪枝的节点数

// 时间控制
clock_t start_time;
double time_limit = 1800.0;  // 时间限制：30分钟

// 检查是否超时
int is_timeout() {
    clock_t current_time = clock();
    double elapsed = ((double)(current_time - start_time)) / CLOCKS_PER_SEC;
    return elapsed > time_limit;
}

// 从文件读取测试数据
Item* load_test_data(const char* filename, int* n) {
    FILE *file = fopen(filename, "r");
    if (file == NULL) {
        printf("无法打开文件 %s\n", filename);
        return NULL;
    }
    
    // 读取物品数量
    fscanf(file, "%d", n);
    
    // 分配内存并读取物品数据
    Item *items = malloc(*n * sizeof(Item));
    
    for (int i = 0; i < *n; i++) {
        fscanf(file, "%d %lf", &items[i].weight, &items[i].value);
    }
    
    fclose(file);
    return items;
}

// 递归蛮力法（带剪枝）
int brute_force_recursive(Item items[], int n, int capacity, int index, 
                         int current_weight, double current_value, int *current_solution) {
    node_count++;
    
    // 每访问一定数量的节点检查超时
    if (node_count % 100000 == 0) {
        if (is_timeout()) {
            return 1;  // 返回超时标志
        }
        
        // 显示进度
        if (node_count % 1000000 == 0) {
            printf("    已访问 %lld 个节点，剪枝 %lld 个节点，当前最优值: %.2f\n", 
                   node_count, pruned_count, best_value);
        }
    }
    
    // 剪枝策略：如果当前重量超过容量，剪枝
    if (current_weight > capacity) {
        // 计算被剪枝的子树大小（2^(n-index) - 1个节点）
        if (n - index <= 60) {  // 避免溢出
            pruned_count += (1LL << (n - index)) - 1;
        } else {
            pruned_count += 1000000;  // 大概估算
        }
        return 0;  // 剪枝，不继续搜索
    }
    
    // 到达叶子节点，检查是否为更优解
    if (index == n) {
        if (current_value > best_value) {
            best_value = current_value;
            best_weight = current_weight;
            memcpy(best_solution, current_solution, n * sizeof(int));
        }
        return 0;
    }
    
    // 递归搜索：不选择当前物品
    current_solution[index] = 0;
    if (brute_force_recursive(items, n, capacity, index + 1, 
                             current_weight, current_value, current_solution)) {
        return 1;  // 传播超时信号
    }
    
    // 递归搜索：选择当前物品
    current_solution[index] = 1;
    if (brute_force_recursive(items, n, capacity, index + 1, 
                             current_weight + items[index].weight, 
                             current_value + items[index].value, current_solution)) {
        return 1;  // 传播超时信号
    }
    
    return 0;
}

// 改进的蛮力法求解0-1背包问题
Result improved_brute_force_knapsack(Item items[], int n, int capacity) {
    Result result = {0};
    result.selected = calloc(n, sizeof(int));
    result.timeout = 0;
    
    printf("    物品数量: %d，开始递归搜索...\n", n);
    
    // 初始化全局变量
    best_value = 0;
    best_weight = 0;
    best_solution = calloc(n, sizeof(int));
    node_count = 0;
    pruned_count = 0;
    
    int *current_solution = calloc(n, sizeof(int));
    
    printf("    开始递归蛮力搜索（带剪枝）...\n");
    start_time = clock();
    
    // 开始递归搜索
    int timeout_flag = brute_force_recursive(items, n, capacity, 0, 0, 0.0, current_solution);
    
    if (timeout_flag) {
        result.timeout = 1;
        printf("    搜索因时间限制而终止\n");
    } else {
        printf("    搜索完成（在时间限制内完成所有搜索）\n");
    }
    
    printf("    总访问节点数: %lld\n", node_count);
    printf("    剪枝节点数: %lld\n", pruned_count);
    if (node_count + pruned_count > 0) {
        double pruning_rate = (double)pruned_count / (node_count + pruned_count) * 100;
        printf("    剪枝率: %.2f%%\n", pruning_rate);
    }
    
    // 复制结果
    result.total_value = best_value;
    result.total_weight = best_weight;
    result.total_nodes = node_count;
    result.pruned_nodes = pruned_count;
    memcpy(result.selected, best_solution, n * sizeof(int));
    
    // 释放内存
    free(best_solution);
    free(current_solution);
    
    return result;
}

// 输出结果到文件
void output_result_to_file(const char* filename, Item items[], int n, Result result) {
    FILE *file = fopen(filename, "w");
    if (file == NULL) {
        printf("无法创建输出文件 %s\n", filename);
        return;
    }
    
    if (result.timeout) {
        fprintf(file, "注意：算法因时间限制(%.0f秒)而提前终止，结果可能不是最优解\n\n", time_limit);
    }
    
    // 输出选择的物品
    fprintf(file, "选择的物品（编号 重量 价值）:\n");
    for (int i = 0; i < n; i++) {
        if (result.selected[i]) {
            fprintf(file, "%d %d %.2f\n", i + 1, items[i].weight, items[i].value);
        }
    }
    
    // 输出总重量、总价值和时间开销
    fprintf(file, "总重量: %d\n", result.total_weight);
    fprintf(file, "总价值: %.2f\n", result.total_value);
    fprintf(file, "时间开销: %.6f 秒\n", result.time_cost);
    
    // 输出搜索统计信息
    fprintf(file, "访问节点数: %lld\n", result.total_nodes);
    fprintf(file, "剪枝节点数: %lld\n", result.pruned_nodes);
    if (result.total_nodes + result.pruned_nodes > 0) {
        double pruning_rate = (double)result.pruned_nodes / (result.total_nodes + result.pruned_nodes) * 100;
        fprintf(file, "剪枝率: %.2f%%\n", pruning_rate);
    }
    
    if (result.timeout) {
        fprintf(file, "状态: 因时间限制提前终止\n");
    } else {
        fprintf(file, "状态: 完整搜索完成\n");
    }
    
    fclose(file);
}


int main() {
    printf("=== 改进蛮力法测试器（递归+剪枝版本） ===\n");
    
    
    // 物品数量数组
    int item_counts[] = {1000};
    int num_item_counts = sizeof(item_counts) / sizeof(item_counts[0]);
    
    // 背包容量数组
    int capacities[] = {10000};
    int num_capacities = sizeof(capacities) / sizeof(capacities[0]);
    
    printf("\n开始改进蛮力法测试...\n");
    printf("时间限制: %.0f 秒\n", time_limit);
    printf("优化策略: 重量剪枝（超重组合及其超集直接剪枝）\n");
    printf("搜索结构: 递归二叉树\n\n");
    
    // 对每个物品数量
    for (int i = 0; i < num_item_counts; i++) {
        int item_count = item_counts[i];
        char data_filename[100];
        sprintf(data_filename, "items_%d.txt", item_count);
        
        printf("加载数据文件: %s\n", data_filename);
        
        int n;
        Item *items = load_test_data(data_filename, &n);
        
        if (items == NULL) {
            printf("跳过文件: %s\n", data_filename);
            continue;
        }
        
        // 对每个背包容量进行测试
        for (int j = 0; j < num_capacities; j++) {
            int capacity = capacities[j];
            
            printf("  测试容量 %d:\n", capacity);
            
            clock_t test_start = clock();
            Result result = improved_brute_force_knapsack(items, n, capacity);
            clock_t test_end = clock();
            
            result.time_cost = ((double)(test_end - test_start)) / CLOCKS_PER_SEC;
            
            // 生成输出文件名
            char output_filename[200];
            sprintf(output_filename, "brute_force_%d_%d.txt", item_count, capacity);
            
            output_result_to_file(output_filename, items, n, result);
            
            if (result.timeout) {
                printf("    完成 (%.6f秒, 价值=%.2f, 提前终止, 剪枝率=%.2f%%)\n", 
                       result.time_cost, result.total_value,
                       (double)result.pruned_nodes / (result.total_nodes + result.pruned_nodes) * 100);
            } else {
                printf("    完成 (%.6f秒, 价值=%.2f, 完整搜索, 剪枝率=%.2f%%)\n", 
                       result.time_cost, result.total_value,
                       (double)result.pruned_nodes / (result.total_nodes + result.pruned_nodes) * 100);
            }
            
            if (result.selected != NULL) {
                free(result.selected);
            }
        }
        
        free(items);
        printf("\n");
    }
    
    printf("改进蛮力法测试完成！\n");
    return 0;
}